Discussion:Algorithme d'Euclide étendu

Liens externe

Bonjour, le liens ne fonctionne pas. Pourriez-vous le modifier ou le supprimer. Merci. CaptainHaddock 28 novembre 2005 à 00:58 (CET)

Javascript

Ce programme faisait partie de l'article jusqu'au 1er novembre 2008. Je l'ai remplacé par une description de l'algorithme impératif. Proz (d) 1 novembre 2008 à 21:59 (CET)

---

Voici en Javascript l'implémentation de l'algorithme d'Euclide étendu qui devrait fonctionner dans la plupart des navigateurs :

// Ce programme ne fonctionne qu'avec des entiers naturels
// demande les données à l'utilisateur et convertit les chaînes de caractères en entiers
var a = parseInt(prompt("Entrer un entier naturel  a",0))
var b = parseInt(prompt("Entrer un entier naturel  b",0))

// On sauvegarde les valeurs de a et b.
a0 = a;
b0 = b;

// Initialisations. On laisse invariant p*a0 + q*b0 = a et  r*a0 + s*b0 = b.
p = 1; q = 0;
r = 0; s = 1;

// La boucle principale:
while (b != 0) { 
  c = a % b;
  quotient = Math.floor(a/b);  //Javascript n'a pas d'opération de division entière.
  a = b;
  b = c;
  nouveau_r = p - quotient * r; nouveau_s = q - quotient * s;
  p = r; q = s;
  r = nouveau_r; s = nouveau_s;
}

// Affiche le résultat.

alert("pgcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)

---

programme

article évidemment à compléter (complexité ébauchée, applications, généralisations ...). Faut-il garder le programme javascript ? On pourrait donner un programme impératif dans un langage où il s'exprime plus simplement. Celui-ci est un peu lourd, mais montre qu'il faut gérer les affectations de variables quand on ne peut les faire simultanément ... Proz 23 juin 2007 à 23:29 (CEST)

tant qu'à illustrer ce genre d'article par un programme, ne faudrait-il pas employer un langage plus carré et plus pédagogique comme l'Ada ? --91.163.58.42 (d) 2 juillet 2008 à 10:54 (CEST)

Pour information, je l'ai réécrit en Python, qui me semble être un des langages les plus simple à comprendre :

# Ce programme ne fonctionne qu'avec des entiers naturels
# demande les données à l'utilisateur et convertit les chaînes de caractères en entiers

a=input("a=")
b=input("b=")

# On sauvegarde les valeurs de a et b.
a0 = a
b0 = b
 
# Initialisations. On laisse invariant p*a0 + q*b0 = a et  r*a0 + s*b0 = b.
p = 1
q = 0
r = 0
s = 1

# La boucle principale:
while b!=0:
    c = a % b
    quotient = a%b
    a = b
    b = c
    nouveau_r = p - quotient * r
    nouveau_s = q - quotient * s
    p = r
    q = s
    r = nouveau_r
    s = nouveau_s

# Affiche le résultat.
print "pgcd(",a0,",",b0,")=",a

message ajouté le 10 septembre 2008 à 23:00 par Utilisateur:BafS

En python on peut justement faire plus concis (affectation simultanée, pas besoin des nouveau_) ... et juste (quotient : / et non %). Hum ... tout ça milite pour supprimer le javascript ;). Par contre le python (bien écrit) apportera-t-il vraiment quelque chose ? C'est quand même assez évident une fois qu'on a la description récursive de l'algorithme. Proz (d) 11 septembre 2008 à 02:16 (CEST)

Je propose une autre version de la multiplication modulo inverse qui me parait plus simple et plus courte que celles proposées

On recherche itérativement le résultat à l'intérieur d'une boucle infinie qui sera interrompue quand la variable j aura la bonne valeur. La traduction en C, Perl, Java, Python... me semble facile

Si vous essayez le deuxième exemple vous trouverez d'autres valeurs(je crois que l'on dit congrues)

PapyJohn

Function MultModInv(A,B: dword): dword

var j: dword;
begin
  J:=1;
  repeat
   if (A * j) mod B = 1 then
    begin
     result:=J;
     exit
    end;
  inc(j);
 until 1<>1;
end;

Function MultModInv(A,B: dword): dword

var j: dword;
begin
  Offset:=0;
  for j:=1 to 10000 do
   if (A * j) mod B = 1 then
    begin
     Inc(Offset)
     Resa[offset]:=j;
    
    end;
  inc(j);
 until 1<>1;
end;

ce commentaire non signé a été ajouté le 30 octobre 2008 par IP88.189.248.160

Je ne suis pas pour ma part favorable à la présentation d'un programme au sein de l'article. On risque de voir alors apparaître autant de programmes que de langages ou même que de contributeurs. L'exemple ci-dessus illustre bien mes propos. Il présente une autre façon de trouver un nombre J tel que AJ soit congru à 1 modulo B. Il permet effectivement de trouver deux nombres J et K tels que AJ + Bk = 1 mais c'est un balayage et ce n'est pas un programme illustrant l'algorithme d'Euclide, sujet de cet article. HB (d) 30 octobre 2008 à 15:03 (CET)

D'accord qu'il ne s'agit pas d'un forum de programmeur qu'il ne faut pas mélanger les genre Mais comment je suis arrivé la? L'exemple me semble intéressant: j'ai chercher a savoir comment on calculait une division inverse modulo pour créer des clefs de cryptographie

Je suis arrivé à l'algo d'Euclide:pour moi est la multiplication inverse modulo. Comme j'ai trouve une solution plus courte mais lente. Je donne la méthode pensant qu'il s'agit d'une autre manière d'aborder l'algo d'Euclide Et voila pour quoi j'ai posté; cela me semblait le bon endroit. Mais si l'algo d'Euclide n'est pas la division inverse modulo alors méa culpa sans aucun problème

(Je n'ai pas reussi a faire marcher l'algo en Python qui mùe semble pourtant simple.

Par exemple 7 est l'inverse modulo 9 de 4,

car 4·7 (mod 9) = 28 (mod 9) = 1.

Le code en Python correspond-t-il a cette attente? PapyJohn

attention Papy John, cela fait deux fois qu'en ajoutant un commentaire tu détruis ce qui étais avant ... fais attention à bien écrire tout à la fin des autres textes. Je suis plus matheuse qu'informaticienne mais l'algorithme qui sous-tend ton programme semble correct, je ne peux rien dire en revanche sur la syntaxe (j'ai remarqué un mélange de j et J, un oubli de  ; après exit) . Comme tu le dis toi-même ton algorithme est long, plus long que celui d'Euclide en général. La question de la complexité de l'algorithme est évoquée dans une section de l'article. Pour expliquer très grossièrement, quand les nombres augmentent, le temps d'exécution de ton algorithme est proportionnel à b, le temps d'exécution de l'algorithme d'Euclide est proportionnel à ln(b). HB (d) 30 octobre 2008 à 20:12 (CET)

Merci de tes remarques je prenais grand soin a effacer les testes précédent de peur d'alourdir les messages Mais je n'arrive toujours pas Faire fonctionner l'exemple Pour info mon code est en Pascal(un langage pour mathématicien). J'ai de fait oublier de supprimer deux lignes dans la deuxieme version mais il n'y a pas de I

Function MultModInv(A,B: dword): dword

var j: dword;
begin
  Offset:=0;
  for j:=1 to 100000 do
   if (A * j) mod B = 1 then
    begin
     Inc(Offset)
     Resa[offset]:=j;   
    end;
end;

PapyJohn

Cette page est destinée à des discussions permettant dde faire progresser l'article. Personne n'y corrige les programmes qui y sont présents, et d'ailleurs celui en python est faux (le quotient c'est a/b), et n'exploite pas la concision du langage. Comme te l'a écrit HB, le programme par recherche exhaustive que tu proposes est hors sujet (de plus le temps d'exécution indiqué signifie qu'il est inutilisable pour des nombres un peu grands tels ceux utilisés en crypto). Si tu t'intéresses à l'algorithme d'Euclide étendu, tu peux indiquer ici ce qui ne te parait pas clair dans l'article, et pourrait être amélioré. Proz (d) 1 novembre 2008 à 22:24 (CET)

Comme je l'ai dis j'arrivai par la multiplication modulo inverse et je n'ai pas trouve clairement le lien qu'il y avait entre les deux. C'est maintenant chose faite j'ai bien trouve mais peut etre serait-il interressant de faire le lien dans l'autre sens. Celui qui lit l'article peut etre interressé par la multiplication mùodulaire inverse et cela donne de la coherence dans la navigation Mais continuez c'est super chouette Papy

PS je suis malvoyant mais merci sincerement d'utiliser une si grande police et cette charte de couleurs simple. C'est essentiel pour moi....

Mon grain de sel en Haskell

eucl(r, u, v, 
     0, _, _) = (r, u, v)
eucl(r , u , v ,
     r', u', v') = let (q,r'') = divMod r r' 
                       in eucl(r' ,  u'    ,  v'    ,
                               r'',  u-q*u',  v-q*v')
euclide a b = eucl(a, 1, 0,
                   b, 0, 1)

C'est un copié collé de la formule de l'article, en bien plus lisible en ce qui me concerne. Les seules clés pour comprendre ce code sont que let permet des déclarations locales et que divMod a b vaut (q, r) vérifiant a = q * b + r [24 mai 2012, non signé]

Ajout : Deux petites chose, la première c'est que bien que la fonction soit recursive terminale, haskell n'en a à priori pas grand chose à faire, l'évaluation paresseuse fait qu'au cours de l'execution, seule l'évaluation 4ième paramètre et effectée. La seconde : Est-ce qu'une implémentation a sa place dans un article ? [26 mai 2012, non signé]

Le problème du code dans les articles c'est que quand on commence à utiliser un langage, chacun va vouloir ajouter celui qu'il préfère, d'où ce choix courant de pseudo-code alors que parfois le code d'un langage bien choisi est très lisible. La tendance générale est d'éviter. Mon avis est qu'il ne faudrait le faire que si ça apporte quelque chose de nouveau. Dans ce cas particulier je suis d'accord que le code Haskell est effectivement très lisible (il suffirait d'ajouter un commentaire pour divMod), mais en même temps ça n'apporte rien au programme équationnel récursif qui y est déjà. Proz (d) 26 mai 2012 à 16:09 (CEST)

Solution minimale

Il manque un énoncé (à prouver ou au moins sourcer) disant, comme dans en:Extended Euclidean algorithm#Description of the algorithm, que cet algorithme fournit l'une des 2 "solutions minimales". Et dans Théorème de Bachet-Bézout, une mention de l'existence d'une telle solution. Anne (discuter) 26 février 2014 à 21:23 (CET)